//题目:
// 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
// candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。 
// 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
    int target;
    vector<int> v;
    vector<vector<int>> ret;
public:
    //法一:
    // void dfs(vector<int>& candidates,int pos,int sum)
    // {
    //     if(sum>target)return;
    //     if(sum==target){
    //         ret.push_back(v);
    //         return;
    //     }

    //     for(int i=pos;i<candidates.size();i++)
    //     {
    //         v.push_back(candidates[i]);

    //         dfs(candidates,i,sum+candidates[i]);
    //         //回溯
    //         v.pop_back();
    //     }
    // }
    // vector<vector<int>> combinationSum(vector<int>& candidates, int t) 
    // {
    //     target=t;

    //     dfs(candidates,0,0);

    //     return ret;
    // }

    //法二:
    void dfs(vector<int>& candidates,int pos,int sum)
    {
        if(sum==target){
            ret.push_back(v);
            return;
        }
        if(sum>target || pos==candidates.size())return;
        
        for(int count=0;sum+count*candidates[pos]<=target;count++)
        {
            if(count>0)v.push_back(candidates[pos]);
            dfs(candidates,pos+1,sum+count*candidates[pos]);
        }
        //回溯
        for(int count=0;sum+count*candidates[pos]<=target;count++)
            if(count>0)v.pop_back();
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int t) 
    {
        target=t;
        dfs(candidates,0,0);

        return ret;
    }
};